LeetCode 75 Level 1 - Day 2 String

205. Isomorphic Strings

• 題目連結
• 難易度：Easy

題目敘述

Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

預設函數

bool isIsomorphic(char * s, char * t){

}

題目輸入限制

• 
• 
• s and t consist of any valid ascii character.

解題過程及程式碼

從今天開始的題目主題是 String，在C語言中都是以字元陣列來表示字串(string)，特別的地方是字元陣列都要以 '\0' 這個特殊字元來結尾，如圖Fig. 1所示，字元陣列裡依次儲存的是'a' 'p' 'p' 'l' 'e'，最後是 '\0'。

這個特性使得字元陣列在傳遞時可以不需要再給陣列的長度，可以經由固定的結尾 '\0' 來計算長度，如下方程式碼，由 i 就可以得到字元陣列的長度。

int i = 0;
while (s[i] != '\0') {
    i++;
}

Leetcode也可以使用C語言內建的string函數，例如strlen(const char *)用來回傳字元陣列的大小，strcmp(const char *, const char *)用來比較2個字串的字典大小，這些都會在後面題目使用。由題目所知，我們就像在對字串進行編碼和解碼，將特定字母替換成特定字母後，看看是否可以還原成原來的字串。

• 想法是去檢查字元是否有被對應過，有重複對應就不合格，我們來看3個例子
  • 1. 如圖Fig. 3所示，輸入字串 s 和 t 分別是paper和title，p對應t、a對應i、e對應l、r對應e，只要一個元素不要對應到二個元素即可，也可以對應到自己，於是paper和title就可以通過。
       
  • 2. 在圖Fig. 4中，輸入字串 s 和 t 分別是foo和bar，f對應p、o對應a、o對應r，o就對應到了2個字元，於是foo和bar就無法通過。
       
  • 3. 注意 s 的對應要檢查相對 t 的對應也要檢查，例如圖Fig. 5中，輸入字串 s 和 t 分別是badc和baba，從 s 來看的對應是b到b、a到a、d到b、c到a可通過，但是反過來從 t 看的對應是b到b、a到a、b到d、a到c，其中 t 的對應裡 b 就重複對到了b和d、a就重複對到了a和c，於是無法通過。
       
• 程式碼上傳

/* 最後上傳 */
bool isIsomorphic(char * s, char * t){
    return !(isConflict(s, t) || isConflict(t, s));  // 對調s, t順序確認字元對應
}
bool isConflict(char * s, char * t) {
    int i = 0;
    int char_table[128] = {0};  // 可記錄所有ascii元素對應

    while (s[i] != '\0') {
        if ((char_table[s[i]] != 0) && (char_table[s[i]] != t[i])) {
            return 1;
        } else {
            char_table[s[i]] = t[i];
        }
        i++;
    }
    return 0;
}

• 最後注意測試項字元陣列不只是包含小寫字母，題目中說明了"s and t consist of any valid ascii character."

今天到這裡結束，謝謝大家，明天見。